package main

import "fmt"

/*
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = "()"
输出：true

示例2：
输入：s = "()[]{}"
输出：true

示例3：
输入：s = "(]"
输出：false

示例4：
输入：s = "([)]"
输出：false

示例5：
输入：s = "{[]}"
输出：true
*/

func isValid(s string) bool {
	if len(s)%2 == 1 {
		return false
	}

	if s == "" {
		return true
	}

	hash := map[byte]byte{')': '(', ']': '[', '}': '{'}
	stack := make([]byte, 0)

	for i := 0; i < len(s); i++ {
		if s[i] == '(' || s[i] == '[' || s[i] == '{' { //如果i是任意一个左括号
			stack = append(stack, s[i])
		} else if len(stack) > 0 && stack[len(stack)-1] == hash[s[i]] { //否则i为右括号 栈里有元素 且 栈顶元素为右括号对应的左括号
			stack = stack[:len(stack)-1] //出栈
		} else {
			return false
		}
	}
	return len(stack) == 0
}

func main() {
	fmt.Println(isValid("([]{})"))
}
